package lanqiaoTraining;

/**
 * @Author liangzai
 * @Description:
 */
public class Main {
    //买卖股票的最佳时机 3
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        int[][] fp = new int[n][3];
        dp[0][0] = -prices[0]; dp[0][1] = -0x3f3f3f3f; dp[0][2] = -0x3f3f3f3f;
        fp[0][0] = 0; fp[0][1] = -0x3f3f3f3f; fp[0][2] = -0x3f3f3f3f;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Math.max(dp[i-1][j],fp[i-1][j]-prices[i]);
                fp[i][j] = fp[i-1][j];
                if(j>=1){
                    fp[i][j] = Math.max(fp[i][j],dp[i-1][j-1]+prices[i]);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < 3; i++) {
            max = Math.max(max,fp[n-1][i]);
        }
        return max;
    }

    //买卖股票的最佳时机 4
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][k+1];
        int[][] fp = new int[n][k+1];
        dp[0][0] = -prices[0];
        fp[0][0] = 0;
        for (int i = 1; i < k+1; i++) {
            dp[0][i] = -0x3f3f3f3f;
            fp[0][i] = -0x3f3f3f3f;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k+1; j++) {
                dp[i][j] = Math.max(dp[i-1][j],fp[i-1][j]-prices[i]);
                fp[i][j] = fp[i-1][j];
                if(j>=1){
                    fp[i][j] = Math.max(fp[i][j],dp[i-1][j-1]+prices[i]);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < k+1; i++) {
            max = Math.max(max,fp[n-1][i]);
        }
        return max;
    }
}
